<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            /* 
            路径总和说白了就是找出所有路径判断值是否为target
            思路：dfs找出所有路径
            终止条件 即叶子节点。需要当前节点存在且左右子节点不存在
            如何让当前节点存在，很简单，每次进入dfs前都判断，只有存在才能dfs
            */
            var hasPathSum = function (root, targetSum) {
                let path = []
                let res = []
                if (!root) return false
                let flag = false
                function dfs(root, path, sum) {
                    //终止条件
                    sum += root.val
                    if (!root.left && !root.right) {
                        if (sum == targetSum) {
                            return (flag = true)
                        }
                    }
                    if (root.left) {
                        dfs(root.left, path, sum)
                    }
                    if (root.right) {
                        dfs(root.right, path, sum)
                    }
                }
                dfs(root, path, 0)
                return flag
            }
        </script>
    </body>
</html>
